package LeetCode2.动态规划;

import java.util.Scanner;

public class LC05 {
    private static int ans = 1;
    private static int begin = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        System.out.println(longestPalindrome(s));
    }
    public static String longestPalindrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()]; // dp[i][j]表示是不是回文串长度
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        for (int len = 2; len <= s.length(); len++) {
            for (int i = 0; i+len-1 <s.length() ; i++) {
                int j = i +len -1;
                if(chars[i] != chars[j]) dp[i][j] = false;
                else {
                    if(len<4) dp[i][j] = true;
                    else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if(len>ans && dp[i][j]){
                    ans = len;
                    begin = i;
                }
            }
        }
        return s.substring(begin,ans+begin);
    }
}
